package algorithm.search.binary.redundency;

/**
 * @program: beauty_of_data_structure_and_algotithm
 * @description: find the first element that is bigger than teh target
 * @author: Keyu Li
 * @create: 2021-09-01 22:53
 **/

public class FindFirstBiggerThanTarget {
    public static int search(int[] arr, int target) {
        return search(arr, target, 0, arr.length - 1);
    }

    public static int search(int[] arr, int target, int lowBound, int highBound) {
        int low = lowBound;
        int high = highBound;
        int mid = (low + high) >> 1;
        while (low <= high) {
            if (arr[mid] >= target) {
                if (mid == lowBound || arr[mid - 1] < target)
                    return mid;
                high = mid - 1;
            } else
                low = mid + 1;
            mid = (low + high) >> 1;
        }
        return -1;
    }

    public static int searchResur(int[] arr, int target, int low, int high) {
        int mid = (low + high) >> 1;
        if (arr[mid] >= target) {
            if (mid == 0 || arr[mid - 1] < target)
                return mid;
            else
                return searchResur(arr, target, low, mid - 1);
        } else
            return searchResur(arr, target, mid + 1, high);
    }
}
